/*
 * unionfind.cpp
 *
 *  Created on: Jun 7, 2011
 *      Author: timothy
 */

#include "unionfind.h"
#include "debug.h"
#include "shingletypes.h"
#include "list.h"

#include <omp.h>
#include <stdlib.h>

// UnionFindEntry

// CONSTRUCTORS //
UnionFindEntry::UnionFindEntry(unsigned long setID)
{
	ID = setID;
	omp_init_lock(&lock);
	Group = NULL;
	Size = 0;
	GroupID = -1;
}
UnionFindEntry::~UnionFindEntry()
{
	omp_destroy_lock(&lock);
}

// METHODS //
void UnionFindEntry::Lock()
{
	if(DEBUG_LEVEL & PDPRINT_THREADING)
	{
		if(!omp_test_lock(&lock))
		{
			pdprint(PDPRINT_THREADING, "Lock contention in union.\n");
			omp_set_lock(&lock);
		}
	}
	else
		omp_set_lock(&lock);

}
void UnionFindEntry::Unlock()
{
	omp_unset_lock(&lock);
}
inline void UnionFindEntry::ForceJoin(UnionFindEntry *target)
{
	this->Group = target;
//	if(target == this) return;
//	// Assume that the path compression was already done.
//	UnionFindEntry *from = this;//PathCompress();
//	UnionFindEntry *to = target;//->PathCompress();
//
//	if(from->ID < to->ID)
//	{
//		pdprint(PDPRINT_UNION, "Joined %ld into %ld.\n", to->ID, from->ID);
//		to->Group = from;
//	}
//	else if (from->ID > to->ID)
//	{
//		pdprint(PDPRINT_UNION, "Joined %ld into %ld.\n", from->ID, to->ID);
//		from->Group = to;
//	}
}
UnionFindEntry *UnionFindEntry::PathCompress()
{
	if(Group == NULL)
	{
		//pdprint(PDPRINT_UNION, "Pathcompress from %d: At root.\n", ID);
		return this;
	}
	else if(Group->Group == NULL)
	{
		//pdprint(PDPRINT_UNION, "Pathcompress from %d: Root is %d.\n", ID, Group->ID);
		return Group;
	}
	else
	{
		//pdprint(PDPRINT_UNION, "Pathcompress from %d: Parent is %d.\n", ID, Group->ID);
		UnionFindEntry *ret = Group->PathCompress();
		Group = ret;
		return ret;
	}
}
void UnionFindEntry::Join(UnionFindEntry *target)
{
	UnionFindEntry *from = this->PathCompress();
	UnionFindEntry *to = target->PathCompress();


	while(1) // Keep trying until it works.
	{
		if(from == to) return; // If we don't need to join, don't interrupt the threads.
		if(from->ID < to->ID)
		{
			from->Lock();
			if(!from->Group && !to->Group)
			{
				from->ForceJoin(to);
				from->Unlock();
				return;
			}
			else
			{
				// Written over. Try again.
				from->Unlock();
//				pdprint(PDPRINT_THREADING, "Written over during union find.\n");
				from = from->PathCompress();
				to = to->PathCompress();
				continue;
			}
		}
		else // to->ID > from->ID
		{
			to->Lock();
			if(!to->Group && !from->Group)
			{

				to->ForceJoin(from);
				to->Unlock();
				return;
			}
			else
			{
				// Written over. Try again.
				to->Unlock();
//				pdprint(PDPRINT_THREADING, "Written over during union find.\n");
				from = from->PathCompress();
				to = to->PathCompress();
				continue;
			}
		}
	}
}

// UnionFindTree
UnionFindTree::UnionFindTree(int size)
{
	array = (UnionFindEntry**)calloc(size, sizeof(UnionFindEntry*));
	nextGroupID = 0;
	groups = 0;
	singletons = 0;
	Size = size;
	for(int i = 0; i < Size; ++i)
		array[i] = new UnionFindEntry(i);
	for(int i = 0; i < omp_get_max_threads(); ++i)
	{
		numCulledInserts[i] = 0;
		numUnculledInserts[i] = 0;
	}
	//omp_init_lock(&table_lock);
}
UnionFindTree::~UnionFindTree()
{
	for(int i = 0; i < Size; ++i)
		delete(array[i]);
	free(array);
}

void UnionFindTree::Insert(Shingle *insert, int nthShingle)
{
	numUnculledInserts[omp_get_thread_num()]++;

	SLE_t topElems[g_ArgVars->shingle_length];
	Shingle::FindTopSElems(topElems, insert->Neighbors, nthShingle);
//	pdprint(PDPRINT_ALL, "(%ld %ld) (%ld %ld) (%ld %ld)\n",
//			topElems[0].value, topElems[0].vertex,
//			topElems[1].value, topElems[1].vertex,
//			topElems[2].value, topElems[2].vertex);

	for(unsigned int i = 0; i < g_ShingleContext->s; ++i)
	{
		Join(topElems[0].vertex, topElems[i].vertex);
		Join(insert->vertices[i], topElems[0].vertex);
	}

}
void UnionFindTree::Join(unsigned long a, unsigned long b)
{
//	pdprint(PDPRINT_UNION, "Joining %d and %d\n", a, b);
	if(array[a]->PathCompress() == array[b]->PathCompress()) return;
	array[a]->Join(array[b]);
}

int UnionFindTree::GetGroupID(unsigned long index)
{
	UnionFindEntry *found = array[index]->PathCompress();
	if(found->GroupID == -1)
		found->GroupID = nextGroupID++;
	if(DEBUG_LEVEL & (PDPRINT_DIAGNOSTICS | PDPRINT_UNION))
	{
		if(found == array[index])
			GroupSizes.push_back(&found->Size);
	}
	return found->GroupID;
}

int UnionFindTree::GetNumberOfGroups()
{
	return groups;
}
int UnionFindTree::GetNumberOfSingletons()
{
	return singletons;
}
void UnionFindTree::AddVertexToAudit(unsigned long vertex)
{
	UnionFindEntry *found = array[vertex]->PathCompress();
	if(found->Size == 0)
	{
		found->Size = 1;
		singletons++;
	}
	else
	{
		if(found->Size == 1)
		{
			singletons--;
			groups++;
			found->Size++;
		}
		else if(found->Size > 1)
		{
			found->Size++;
		}
	}
}
void UnionFindTree::AddEdgeToAudit(unsigned long from, unsigned long to)
{
	TotalEdges++;
	UnionFindEntry *g1 = array[from]->PathCompress();
	UnionFindEntry *g2 = array[to]->PathCompress();
	if(g1 == g2)
	{
		g1->NumberOfEdges++;
	}
	else if(g1->Size == 1 || g2->Size == 1)
	{
#ifndef MERGE_ON_SINGLETONS
		SingletonEdges++;
#else
		Join(from, to);
		UnionFindEntry *gNew = g1->PathCompress();
		if(g1->Size == 1)
		{
			singletons--;
		}
		if(g2->Size == 1)
		{
			singletons--;
		}
		if(g2->Size == 1 && g1->Size == 1)
		{
			groups++;
		}
		gNew->Size = g1->Size + g2->Size;
		gNew->NumberOfEdges = g1->NumberOfEdges + g2->NumberOfEdges + 1;
#endif
	}
	else
	{
		ExternalEdges++;
	}
}
void UnionFindTree::AuditEdges()
{
	printf("%d singleton edges and %d external edges of %d total edges.\n", SingletonEdges, ExternalEdges, TotalEdges);
}
void UnionFindTree::AuditGroupSizes()
{
	if(!(DEBUG_LEVEL & (PDPRINT_DIAGNOSTICS | PDPRINT_UNION)))
		return;
	int lineCount = -1;
	for(unsigned int i = 0; i < GroupSizes.size(); ++i)
	{
		if(*GroupSizes[i] > 1)
		{
			if(lineCount++ >= 0)
			{
				if(lineCount % 5 == 0)
					printf("\n");
				else
					printf(",  ");
			}
			printf("Group %7d: %7d", i, *GroupSizes[i]);
		}
	}
	printf("\n");
}
